package Aleehot100;

import C017.main;

import java.util.HashMap;

/**
 * ClassName: c035
 * Package: Aleehot100
 * Description: LRU 缓存
 *
 * @Author BCXJ
 * @Create 2025/7/1 08:46
 * @Version 1.0
 * @Since 1.0
 */
public class c035 {

    public static void main(String[] args) {
//        LRUCache lruCache = new LRUCache(2);
//        lruCache.put(1,0);
//        lruCache.put(2,2);
//        System.out.println(lruCache.get(1));
//        lruCache.put(3,3);
//        System.out.println(lruCache.get(2));
//        lruCache.put(4,4);
//        System.out.println(lruCache.get(1));
//        System.out.println(lruCache.get(3));
//        System.out.println(lruCache.get(4));


//        LRUCache lruCache = new LRUCache(2);
//        lruCache.put(2, 6);
//        lruCache.put(1, 5);
//        lruCache.put(1, 2);
//        System.out.println(lruCache.get(1));
//        System.out.println(lruCache.get(2));

//        LRUCache lruCache = new LRUCache(2);
//        lruCache.put(2, 1);
//        lruCache.put(2, 2);
//        System.out.println(lruCache.get(2));

//        LRUCache lruCache = new LRUCache(1);
//        System.out.println(lruCache.get(1));
//        lruCache.put(1, 2);
//        lruCache.put(1, 3);
//        lruCache.put(12, 3);
//        lruCache.put(3, 3);
//        System.out.println(lruCache.get(1));


//        LRUCache lruCache = new LRUCache(3);
//        lruCache.put(1,1);
//        lruCache.put(2,2);
//        lruCache.put(3,3);
//        lruCache.put(4,4);
//        System.out.println(lruCache.get(4));
//        System.out.println(lruCache.get(3));
//        System.out.println(lruCache.get(2));
//        System.out.println(lruCache.get(1));
//        lruCache.put(5,5);
//        System.out.println(lruCache.get(1));
//        System.out.println(lruCache.get(2));
//        System.out.println(lruCache.get(3));
//        System.out.println(lruCache.get(4));
//        System.out.println(lruCache.get(5));

        LRUCache lruCache = new LRUCache(1);
        lruCache.put(1, 2);
        System.out.println(lruCache.get(1));
    }

    static class LRUCache {

        int capacity;
        int size;
        HashMap<Integer, Node> container = new HashMap<>();
        DoubleLinkedList list = new DoubleLinkedList();

        // 双向链表结构
        static class Node {
            int key;
            int val;
            Node last;
            Node next;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }

        class DoubleLinkedList {
            Node head;
            Node tail;

            // 节点移动到头部
            public void moveToHead(Node node) {
                // node 是头节点
                if(node == head) {
                    return;
                }
                // 尾节点
                if (node == tail) {
                    tail = tail.last;
                    tail.next = null;
                    node.last = null;
                    head.last = node;
                    node.next = head;
                    head = node;
                    return;
                }
                // 中间节点
                node.last.next = node.next;
                node.next.last = node.last;
                node.next = head;
                head.last = node;
                node.last = null;
                head = node;
            }

            // 节点移动到尾部
            public void moveToTail(Node node) {
                // node 是尾结点
                if(node == tail) {
                    return;
                }
                // node 是头节点
                if(node == head) {
                    head = head.next;
                    head.last = null;
                    node.next = null;
                    tail.next = node;
                    node.last = tail;
                    tail = node;
                    return;
                }
                // node是中间节点
                node.last.next = node.next;
                node.next.last = node.last;
                tail.next = node;
                node.last = tail;
                node.next = null;
                tail = node;
            }

            // 删除尾结点
            public void removeTail() {
                container.remove(tail.key);
                tail = tail.last;
                if(tail != null) {
                    tail.next = null;
                } else {
                    head = null;
                }
                size--;
            }

            // 增加节点并移动到头部
            public void add(Node node) {
                node.next = head;
                if(head != null) {
                    head.last = node;
                    head = node;
                } else {
                    head = node;
                    tail = node;
                }
            }

            public void setHead(Node head) {
                this.head = head;
            }
            public void setTail(Node tail) {
                this.tail = tail;
            }

        }

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            Node node = container.get(key);
            if(node == null) {
                return -1;
            }
            list.moveToHead(node);
            return node.val;
        }

        public void put(int key, int value) {
            // 未满，插入元素并 移到链表头部
            if(!container.containsKey(key)) {
                Node node = new Node(key, value);
                // 容量满，去除元素
                if(size == capacity) {
                    list.removeTail();
                }
                container.put(key, node);
                list.add(node);
                size ++;
            } else {
                container.get(key).val = value;
                list.moveToHead(container.get(key));
            }

        }
    }


}
































//class LRUCache {
//    class Node {
//        int key;
//        int val;
//        Node last;
//        Node next;
//
//        public Node(int key, int val) {
//            this.key = key;
//            this.val = val;
//        }
//    }
//
//    class DoubleLinkedList {
//        Node head;
//        Node tail;
//
//        /**
//         * @param node
//         */
//        public void moveToTail(Node node) {
//            if (node == null) {
//                return;
//            }
//            if (tail == node) {
//                return;
//            }
//            // 如果是头节点
//            if (head == node) {
//                head = head.next;
//                if (head != null) { // 如果元素只有一个的话, 避免NULL异常
//                    head.last = null;
//                } else {
//                    tail = null;
//                }
//            } else {
//                // 中间节点
//                node.last.next = node.next;
//                node.next.last = node.last;
//            }
//            tail.next = node;
//            node.last = tail;
//            node.next = null;
//            tail = node;
//        }
//
//        // 增加元素
//        public void add(Node node) {
//            if (node == null) {
//                return;
//            }
//
//            // 如果链表为null
//            if (head == null) {
//                head = node;
//                tail = node;
//                return;
//            }
//            // 正常链表
//            tail.next = node;
//            node.last = tail;
//            tail = node;
//        }
//
//        /**
//         * 溢出头元素
//         *
//         * @return
//         */
//        public Node remove() {
//            if (head == null) {
//                return null;
//            }
//            Node res = head;
//            head = head.next;
//            if (head != null) {
//                head.last = null;
//            } else {
//                tail = null;
//            }
//            return res;
//        }
//    }
//
//    HashMap<Integer, Node> map = new HashMap<>();
//    int capacity;
//    DoubleLinkedList list = new DoubleLinkedList();
//
//    public LRUCache(int capacity) {
//        this.capacity = capacity;
//    }
//
//    /**
//     * 增加元素
//     *
//     * @param k
//     * @param v
//     */
//    public void put(int k, int v) {
//        if (map.containsKey(k)) {
//            // 修改元素
//            Node node = map.get(k);
//            node.val = v;
//            // 修改元素的双向链表的位置
//            list.moveToTail(node);
//        } else {
//            // 如果容量不足
//            if (map.size() == capacity) {
//                Node node = list.remove();
//                map.remove(node.key);
//            }
//            // 增加元素
//            Node node = new Node(k, v);
//            map.put(k, node);
//            list.add(node);
//        }
//    }
//
//    public int get(int k) {
//        if (map.containsKey(k)) {
//            Node node = map.get(k);
//            // 调整node的双向链表的位置
//            list.moveToTail(node);
//            return node.val;
//        } else {
//            return -1;
//        }
//    }
//}
//
///**
// * Your LRUCache object will be instantiated and called as such:
// * LRUCache obj = new LRUCache(capacity);
// * int param_1 = obj.get(key);
// * obj.put(key,value);
// */
